
package com.wangwei.sort;

/**
 * 希尔排序
 */
public class Shell extends Example {
    @Override
    public void sort(Comparable[] arr) {
        int N = arr.length;
        int h = 1;
        while (h<N/3) h =3*h +1;
        while (h >= 1){
            for(int i=h;i<N;i++){
                for(int j=i; j>=h && less(arr[j],arr[j-h]) ; j-=h){
                    exch(arr,j,j-h);
                }
            }
            h = h/3;
        }
    }

    public static void main(String[] args) {
        String [] arr = {"A","S","D","F","G","H","J","K","L"};
        Example example = new Shell();

        example.sort(arr);
        assert example.isSorted(arr);
        example.show(arr);
    }
}
